package leetcode_day._2023._11;

import java.util.ArrayList;
import java.util.List;

/**
 * 2216.美化数组的最少删除数 <br />
 * 算法: 模拟 + 贪心 + 栈(可以不用)
 *
 * @author yezh
 * @date 2023/11/21 11:01
 */
public class _21 {

    public int minDeletion_stack(int[] nums) {
        int ans = 0, n = nums.length;
        List<Integer> st = new ArrayList<>(n);
        for (int num : nums) {
            // 遇到一样的就删
            while (!st.isEmpty() && st.get(st.size() - 1) == num) {
                st.remove(st.size() - 1);
                ++ans;
            }
            if (st.isEmpty()) st.add(num);
            else {
                if (st.get(st.size() - 1) != num) st.remove(st.size() - 1);
                else st.add(num);
            }
        }
        return ans + st.size();
    }

    public int minDeletion(int[] nums) {
        int n = nums.length, cnt = 0;
        for (int i = 0, idx; i < n - 1; i++) {
            idx = i - cnt;
            if (idx % 2 == 0 && nums[i] == nums[i + 1]) ++cnt;
        }
        return (n - cnt) % 2 == 0 ? cnt : cnt + 1;
    }

}
